#define _CRT_SECURE_NO_WARNINGS 1
class Solution
{
	bool vis[16][16];
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
	int m, n;
	int ret;
public:
	int getMaximumGold(vector<vector<int>>& g)
	{
		m = g.size(), n = g[0].size();
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
			{
				if (g[i][j])
				{
					vis[i][j] = true;
					dfs(g, i, j, g[i][j]);
					vis[i][j] = false;
				}
			}
		return ret;
	}
	void dfs(vector<vector<int>>& g, int i, int j, int path)
	{
		ret = max(ret, path);
		for (int k = 0; k < 4; k++)
		{
			int x = i + dx[k], y = j + dy[k];
			if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y])
			{
				vis[x][y] = true;
				dfs(g, x, y, path + g[x][y]);
				vis[x][y] = false;
			}
		}
	}
};